package codingPractice.huawei;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class dijkstra {
    public static class node {
        int x;  //节点编号
        int length; //长度
        public node (int x, int length) {
            this.x = x;
            this.length = length;
        }
    }
    public static void main(String[] args) {
        int[][] map = new int[6][6];    //记录权值，顺便记录链接情况
        initmap(map);  //初始化
        boolean bool[] = new boolean[6];   //判断是否已经确定从起点到该点的最短距离
        int len[] = new int[6];   //从起点到达每个点的最短长度
        for(int i=0; i<6; i++) {
            // 初始化距离为最大值
            len[i] = Integer.MAX_VALUE;
        }
        Queue<node> q1 = new PriorityQueue<node>(com);
        len[0] = 0; //从0这个点开始
        q1.add(new node(0, 0));
        while(!q1.isEmpty()) {
            node t1 = q1.poll();
            int index = t1.x;    //节点编号
            int length = t1.length;   //从起点到当前节点的距离
            bool[index] = true;   //抛出点确定 
            for(int i=0; i<map[index].length; i++) {
                // 是否有index->i: map[index][i]>0
                if(map[index][i] > 0 && !bool[i]) {
                    node node = new node(i, length + map[index][i]);
                    if(node.length < len[i]) {
                        len[i] = node.length;
                        q1.add(node);
                    }
                } 
            }
        }
        for(int i=0;i<6;i++) {
            System.out.println(len[i]);
        }        
    }

    public static Comparator<node> com = new Comparator<node>() {
        public int compare(node o1, node o2) {
            return o1.length - o2.length;
        }
    };

    private static void initmap(int[][] map) {
        map[0][1]=2;map[0][2]=3;map[0][3]=6;
		map[1][0]=2;map[1][4]=4;map[1][5]=6;
		map[2][0]=3;map[2][3]=2;
		map[3][0]=6;map[3][2]=2;map[3][4]=1;map[3][5]=3;
		map[4][1]=4;map[4][3]=1;
		map[5][1]=6;map[5][3]=3;
    }
}
